package com.bm;

import com.future.util.TreeNode;

/**
 * Description: BM34 判断是不是二叉搜索树
 *
 * @author weiruibai.vendor
 * Date: 2022/9/27 10:13
 */
public class BM34 {

    /**
     * 注意用例 3 2 5 1 4
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        return process(root).isFull;
    }

    private Info process(TreeNode root) {
        if (root == null) {
            return new Info(true, null);
        }
        // 左
        Info left = process(root.left);
        if (!left.isFull) {
            return new Info(false);
        }
        // 又
        Info right = process(root.right);
        boolean isBalance = false;
        if (left.isFull && right.isFull
                && (left.val == null || root.val > left.val) && (right.val == null || root.val < right.val)) {
            isBalance = true;
        }
        // 注意，需要把左边最大值，左边最大值返回，否则可能有错
        int val = Math.max(root.val, root.right.val);
        return new Info(isBalance, val);
    }

    class Info {
        public boolean isFull;

        public Integer val;

        public Info(boolean isFull, Integer val) {
            this.isFull = isFull;
            this.val = val;
        }

        public Info(boolean isFull) {
            this.isFull = isFull;
        }
    }
}
